/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-26
 * Time:22:07
 */
//排序
public class Sort {
    //插入排序
    //1.直接插入排序 - 元素集合越接近有序，直接插入排序算法的时间效率越高
    //直接插入排序是一种简单的插入排序法，其基本思想是：
    //把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列(升序或者降序)。
    //思路(升序)：定义一个变量i，从数组下标为i=1的位置开始遍历，因为第一个元素（下标0）默认是已排序的。也就是说，外层循环的初始位置从i=1开始，
    //在外层循环中，使用变量tmp保存当前待插入的元素array[i]。定义一个变量j，从当前元素i的前一个元素i-1，即j=i-1的位置开始遍历，注意是向前遍历，
    //也就是内层循环的初始位置从i-1开始，在内层循环中，如果array[j]>tmp，那么我们就将array[j]这个较大的元素往后移动一位，
    //即将array[j]移动到j+1的位置上(i的位置上)，array[j+1]=array[j],然后j--，如果array[j]<=tmp，那直接将tmp放到array[j]的后一个位置，
    //即array[j+1]=tmp，然后跳出循环。
    //注意：在内层循环中，如果发现array[j] > tmp，则将array[j]的值向后移动到array[j+1]。如果发现array[j] <= tmp，则说明tmp应该插入
    //到array[j]的后面，也就是array[j+1]的位置，然后我们执行array[j+1] = tmp并跳出内层循环。但是，有一种情况：如果一直比较到j--
    //（也就是所有已排序元素都比tmp大），那么内层循环会因为j>=0条件不满足而退出。此时，我们还没有执行插入操作。所以，在内层循环之后，我们需要
    //将tmp放入正确的位置，这个位置就是j+1（因为此时j为-1，j+1就是0，也就是数组的第一个位置）。所以，array[j+1]=tmp这一行代码包含了以上的两种
    //情况，因此我们可以统一写在内层循环结束之后，也就是说在array[j]<=tmp的情况中，直接break跳出内层循环，不在这里赋值，这样可以避免重复赋值。
    //  总的来说，就是这种情况统一处理了：
    //     * 找到合适位置break的情况
    //     * 比较到数组开头(j=-1)的情况
    public static void insetSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//待插入的元素
            int j = i-1;//从当前元素的前一个开始比较
            //寻找插入位置并移动元素
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    //如果array[j]大于tmp，则将array[j]元素向右移动到j+1的位置，即i的位置
                    array[j+1] = array[j];
                }else {
                    //如果不大于tmp，则break跳出循环(注意，else这里只执行跳出循环，不赋值，统一到下面的一条语句赋值，否则在这里赋值会和下面的
                    //赋值重复操作)
                    break;
                }
            }
            //由于array[j]不大于tmp，那么array[j+1]的位置放的就是tmp / 如果j<0的情况也通过这条语句赋值
            array[j+1] = tmp;
        }
    }
    /*
    直接插入排序时间复杂度：O(N^2) - 平均情况
       最坏情况O(N^2)：逆序的 5 4 3 2 1：对于第i个元素，需要比较i次，移动i次。总操作次数为：2*(1+2+3+...+n-1) = 2 * n(n-1)/2 = n(n-1)
       最好情况O(N)：本身就是有序的 1 2 3 4 5：每次内层循环只需要比较一次就会break（或者进入内层循环的条件不满足，
                                          因为当前元素已经大于等于前一个元素）。所以，对于每个元素，我们只进行了常数次操作。
    空间复杂度：O(1) - 直接插入排序是原地排序算法，只需要常数级别的额外空间。我们只使用了有限的几个变量（如i, j, tmp），所以空间复杂度为O(1)
                    算法只使用了固定数量的额外变量：i, j, tmp 等循环变量和临时变量，无论输入数组多大，这些变量的数量都是固定的
                    原地排序：所有操作都在原数组上进行，不需要额外的数组空间
    稳定性：稳定的排序
        当遇到相等元素时（array[j] == tmp），执行break，不进行交换，相等元素的相对位置保持不变
        ##本身如果是一个稳定的排序，那么可以实现为不稳定的排序(将array[j]>tmp这个条件改成array[j]>=tmp就可以实现将稳定变成不稳定，
          让相等元素也交换)，但是如果本身是不稳定的排序，不能实现为稳定的排序
     */
    //以下的直接插入排序配合思路更清晰
    public static void insetSort1(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            while (j >= 0 && array[j] > tmp) {
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = tmp;
        }
    }

    //2.希尔排序(缩小增量排序)
    //基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
    //希尔排序的思想基于以下两点：
    //1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
    //2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
    //希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长
    //进行排序，最后一步就是普通的插入排序(直接插入排序)，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
    //步骤：
    //1.选择一个增量序列：通常初始增量gap为数组长度的一半，然后每次增量减半，直到增量为1。
    //2.按增量序列个数k，对序列进行k趟排序。
    //3.每趟排序，根据对应的增量gap，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，
    //表长度即为整个序列的长度。
    /*
    时间复杂度：O(n^1.3)~O(n^1.5) [以下写的代码的时间复杂度是O(n*log_2n)]
    空间复杂度：O(1)
    稳定性：不稳定的排序
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            //初始间隔为数组长度的一半，逐步缩小
            gap /= 2;
            //对每个子序列进行插入排序
            shell(array,gap);
        }
    }
    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) { //这里不可以是i+=gap，这样写最后结果是对的，但那是因为最后会整体看作一组进行插入排序
            int tmp = array[i];                    //是i++的话，可能会出现第一组还没有插入完成，就跳到另一组去了，但是不影响，毕竟是
            int j = i-gap;                         //跳跃式插入，另一组与它对应的元素还是会对应上的
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    //方法二
    public static void shellSort1(int[] array) {
        int n = array.length;
        //初始间隔为数组长度的一半，逐步缩小
        for (int gap = n/2; gap > 0 ; gap /= 2) {
            //对每个子序列进行插入排序
            for (int i = gap; i < n; i++) {
                int tmp = array[i];
                int j = i-gap;
                //插入排序
                while (j >= 0 && array[j] > tmp) {
                    array[j+gap] = array[j];
                    j -= gap;
                }
                array[j+gap] = tmp;
            }
        }
    }

    //选择排序
    //1.直接选择排序
    //基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
    //思路：定义一个变量i，从数组的0下标位置开始遍历，在外层循环中，定义一个minIndex变量，它是用来存放数组中最小元素的下标的，每次假设最小值是下标
    //为i上的元素；定义一个变量j，它从i的下一个位置开始遍历数组，即j=i+1，在内层循环中，如果判断array[j] < array[minIndex]，那么更新新的最
    //小元素的下标minIndex为j位置上的元素，即minIndex=j，直到将数组遍历完成，跳出内层循环，此时minIndex最终存储的就是数组中最小元素的下标位置，
    //将i(=0)和minIndex位置上的元素进行交换，此时数组中的第一个元素存放的就是最小元素;最后i++,进行新的一轮遍历，直到数组有序。
    /*
    时间复杂度：O(N^2)  -  和数据是否有序无关
            (第1轮比较了n-1次，第2轮比较n-2次……第n-1轮比较1次，n-1+n-2+……+1=n(n-1)/2)
            总操作次数 = 比较次数 + 交换次数= n(n-1)/2 + (n-1)= O(n²) + O(n) = O(n²)  # 取最高阶项
            最好情况：O(n²) - 数组已经有序，仍需比较 n(n-1)/2 次
            最坏情况：O(n²) - 数组逆序，比较次数相同
    空间复杂度：O(1)
    稳定性：不稳定的排序
     */
    public static void selectSort1(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //上述的排序方法中，即使数组是有序的，依然需要进行比较和交换，那么可以对直接选择排序进行优化，避免不必要的交换和比较
    //思路：同时遍历选出最大元素和最小元素。
    //定义一个变量left，表示数组的第一个元素的下标，定义一个变量right，表示数组的最后一个元素的下标，在left<right的情况下，进入循环，
    //定义一个minIndex，用来存放数组中最小元素的下标，maxIndex用来存放数组中最大元素的下标，初始时它们都为left(0)，定义一个变量i，从数组的第二个
    //元素开始遍历，即i=left+1(i要小于等于right)，进入内层循环，如果array[i]<array[minIndex]，那么更新最小元素的下标为i，即minIndex=i,
    //继续遍历，如果array[i]>array[maxIndex]，那么更新最大元素的下标为i，即maxIndex=i，i遍历直到不符合条件，跳出内层循环，先让left和
    //minIndex位置上的元素交换，这样left存放的就是数组中最小的元素，然后让right和maxIndex位置上的元素交换，这样right存放的就是数组中最大的
    //元素，最后让left++，right--,开始新一轮的遍历，直到数组有序。
    public static void selectSort(int[] array) {
        int left = 0;
        int right = array.length-1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            //如果最大元素的下标刚好是在left下标位置的元素，但是由于上面的一条代码，将left位置上的元素与最小元素进行了交换，此时left位置上的元素
            //是数组中最小的元素，而原先的最大的元素跑到了minIndex下标位置上了，因此，此时需要更新maxIndex，让它指向最大元素的位置，然后再进行
            //交换
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

    //2.堆排序
    //堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
    //需要注意的是排升序要建大堆，排降序建小堆。
    /*
    时间复杂度：O(n*log_2n)
    空间复杂度：O(1)
    稳定性：不稳定的排序
     */
    public static void heapSort(int[] array) {
        createHeap(array);
        //排序
        int end = array.length-1;
        while (end > 0) {
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    private static void createHeap(int[] array) {
        //建大根堆
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
            siftDown(array,parent,array.length);
        }
    }
    private static void siftDown(int[] array,int parent,int length) {
        int child = 2*parent+1;
        while (child < length) {
            if (child+1 < length && array[child] < array[child+1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    //交换排序
    //基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：
    //将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
    //1.冒泡排序
    /*
    时间复杂度：O(N^2) - 讨论没有优化的情况下，也就是没有 boolean元素 和 -i 操作,优化后可以达到O(N)
    空间复杂度：O(1)
    稳定性：稳定的排序(如果变成array[j]>=array[j+1]就会变成不稳定的排序)
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if (!flg) {  //flg == false
                break;
            }
        }
    }

    //2.快速排序
    //基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有
    //元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
    //(1)Hoare划分法快速排序
    //思路：以数组中第一个元素left为基准值，从后边(数组最后一个元素right)开始找到比基准值小的元素停下来，从前边(数组第一个元素)开始找到比基准值大
    //的元素停下来，然后交换left和right位置上的元素，重复循环上述的操作交换元素，直到left和right相遇，停下来，交换基准值和left(right)位置上的
    //元素，此时基准值的左序列都比基准值小，右序列都比基准值大。
    //具体做法：在quick方法中，定义一个变量start，表示数组第一个元素的下标位置，end表示数组最后一个元素的下标位置。写一个方法partition，用来寻找
    //交换过程中start和end相遇的下标位置pivot，在partition方法中，使用tmp变量记录基准值array[left]，并且使用变量tmpLeft记录基准值下标位置
    //left，在left<right的情况下，进入循环，如果array[right]>=tmp,即right位置上的元素大于基准值，则right--，直到找到小于基准值的元素，让
    //right停下来，此时right位置上的元素就是比基准值小的元素；如果array[left]<=tmp，即left位置上的元素小于基准值，则left++，直到找到大于
    //基准值的元素，left停下来，此时left位置上的元素就是比基准值大的元素，让right和left位置上的元素交换位置。然后继续在满足left<right条件下
    //去重复上述的操作。当跳出循环时，说明left和right相遇了，此时让基准值与left(right)位置上的元素交换位置，那么此时基准值的下标不再是
    //tmpLeft(0)的位置，而变成了left的位置，此时left的左边都是比它小的元素，右边都是比它大的元素，返回left(相遇位置)。
    //回到quick方法中，通过partition方法找到了start和end相遇的位置pivot(left)，pivot的左序列都比pivot小，右序列都比pivot大。递归遍历
    //pivot的左右序列，重复之前的操作(左序列的start仍然是原来的，end变成pivot-1；右序列的end是原来的，start变成pivot+1)，
    //在遍历左/右序列的过程中，如果start和end相遇(start==end)，则说明此时递归遍历的序列只有一个元素，那么返回，如果start>end，则说明此时
    //递归遍历的序列是一个空序列，那么也返回。
    //回到quickSort方法中，调用quick方法进行快速排序即可。
    //问题：1.为什么是先从后往前找比基准值大的元素，再从前往后找比基准值小的元素，不能先从前往后找比基准值小的元素，然后从后往前找比基准值大的元素吗
    //—————— 不能，如果这样换完之后不符合基准值的左序列都比基准值小，右序列都比基准值大。
    //2.为什么array[right] >= tmp、array[left] <= tmp 要取等号？
    //—————— 示例：基准值left是6，而right也是6，如果不取等号，那么left/right都进不去循环进行++或者--，那么就会进行交换操作，交换完成之后，
    //还是6和6与基准值6进行比较，会陷入死循环，取等号就可以避免这种情况。
    /*
    时间复杂度：最好情况：O(n*log₂n)
                每次分区都能将数组均匀分成两半，递归树的高度：log₂n，每层的工作量：O(n)，总工作量：n × log₂n = O(nlog₂n)
             最坏情况：O(n²)
                数组已经有序或逆序时，每次分区极度不平衡（一个子数组为空），递归树退化为链表，高度：n，每层工作量：n, n-1, n-2, ..., 1
                总工作量：n(n+1)/2 = O(n²)
    空间复杂度：最好情况：O(log n) - 平衡分区时递归深度
             最坏情况：O(n) - 不平衡分区时递归深度
    稳定性：不稳定的排序
     */
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        if (start >= end) {
            return;
        }
        //优化部分
        //1.
        if (end-start+1 <= 7) {
            insetSortRange(array,start,end);
            return;
        }
        //2.
        //System.out.println("start:"+start+" end:"+end);
        int midIndex = getMiddleNum(array,start,end);
        swap(array,start,midIndex);

        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static int partitionHoare(int[] array, int left, int right) {
        int tmp = array[left];
        int tmpLeft = left;
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,tmpLeft);
        return left;
    }

    //(2)挖坑法快速排序(一般快速排序采用挖坑法)
    //思路：在partition方法中，使用变量tmp保存一下数组中第一个元素(left)，在left<right的情况下，进入循环，当array[right]>=tmp时，即right
    //位置上的元素大于等于tmp时，则right--，直到找到小于tmp的元素，让right停下来，此时right位置上的元素就是比tmp小的元素，让
    //array[left]=array[right]，即right位置上的小的元素放到left位置上；如果array[left] <= tmp，即left位置上的元素小于等于tmp时，
    //则left--，直到找到大于tmp的元素，让left停下来，此时left位置上的元素就是比tmp小的元素，让array[right] = array[left]，即left位置上的
    //大的元素放到之前空出来的right位置。然后继续在满足left<right的情况下，循环遍历上述的操作。当跳出循环时，说明left和right相遇了，将tmp放在
    //left(right)位置上，然后返回left。之后的操作和Hoare法一样。
    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    //(3)前后指针法快速排序
    //思路：在partition方法中，定义一个prev变量，初始时是记录数组中第一个元素的下标位置left，定义一个变量cur，初始时是数组中第二个元素的下标位置
    //left+1，在cur<=right的情况下，进入循环，如果cur位置上的元素小于left位置上的元素并且prev的后一个位置的元素不等于cur位置上的元素，交换
    //cur和prev位置上的元素，cur++。然后继续在满足cur<=right的情况下，重复上述的操作。当跳出循环时，说明cur走到了空，将此时的prev位置上的元素
    //和left(0)位置上的元素交换，然后返回prev。之后的操作和Hoare法一样。
    private static int partition1(int[] array,int left,int right) {
        int prev = left;
        int cur = left+1;
        while (cur <= right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }

    //优化快速排序
    //快速排序在最坏情况下，时间复杂度会退化到O(n^2)，这通常发生在输入数组已经有序或接近有序的情况下，此时分区操作可能极不平衡，可能导致递归深度
    //达到O(n)而引起栈溢出，因此使用三数取中法对快速排序进行优化，能够提高在快速排序过程中每次递归分区将数组均匀分区的概率，降低了最坏情况发生。
    //在quick方法中，每次寻找相遇点pivot之前，使用三数取中法寻找left和right下标的中间位置midIndex，即(left+right)/2，而这个minIndex位置
    //上的元素要将其作为基准值，因此，找到minIndex后，每次让left位置上的元素和midIndex位置上的元素交换位置，保证基准值在前面的位置，
    //接着才开始进行相遇点的寻找。
    //三数取中法 思路：首先根据left和right求出中间下标位置，在array[left]<array[right]的情况下，如果array[mid]<array[left],那么中间
    //位置是left，返回left；如果array[mid]>array[right]，那么中间位置是right，返回right；如果上述的情况都不是，那么mid本身就是中间位置，
    //返回mid。在array[left]>array[right]的情况下，如果如果array[mid]>array[left],那么中间位置是left，返回left；
    //如果array[mid]<array[right]，那么中间位置是right，返回right；如果上述的情况都不是，那么mid本身就是中间位置，返回mid。
    private static int getMiddleNum(int[] array,int left,int right) {
        int mid = (left+right)/2;
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if (array[mid] > array[left]) {
                return left;
            }else if (array[mid] < array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }

    //此外，快速排序是递归算法，递归调用的深度在最坏情况下可能达到O(n)，也容易导致栈溢出，而且快速排序作为递归算法，对小的子区间递归的效率较低
    //所以递归到小的子区间时，可以使用直接插入排序，这样就能减少调用递归的次数。(快速排序在递归时，那些小子数组往往已经基本排好序了,而直接插入排序
    //对基本有序的数组排序特别快，因此使用直接插入排序)
    private static void insetSortRange(int[] array,int start,int end) {
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start; j--) {
                if (array[j] >tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
}
